#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <queue>
using namespace std;
/*
 * @lc app=leetcode.cn id=127 lang=cpp
 *
 * [127] 单词接龙
 */

// @lc code=start
class Solution {
public:
    // bellman-ford算法
    // int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    //     wordList.push_back(beginWord);
    //     vector<int> dp(wordList.size(), 5005);
    //     vector<bool> used(wordList.size(), false);
    //     dp[wordList.size() - 1] = 0; int res = -1;
    //     while (true) {
    //         int u = -1;
    //         for (int i = 0; i < dp.size(); i++) {
    //             if (!used[i] && (u == -1 || dp[u] > dp[i])) u = i;
    //             if (wordList[i] == endWord) res = i;
    //         }
    //         if (res == -1) return 0;
    //         if (u == -1) break;
    //         used[u] = true;
    //         for (int i = 0; i < wordList.size(); i++) {
    //             int d = distance(wordList[i], wordList[u]);
    //             if (d == 1) dp[i] = min(dp[i], dp[u] + 1);
    //         }
    //     }
    //     return dp[res] > 5000 ? 0 : dp[res] + 1;
    // }

    // int distance(const string& beginWord, const string& endWord) {
    //     int d = 0;
    //     for (int i = 0; i < beginWord.size(); i++) {
    //         if (beginWord[i] != endWord[i]) d++;
    //     }
    //     return d;
    // }

    // 相当于使用BFS求最短路径吧, 因为每一条边的权值实际上是一样的
    // 就没有必要使用单点最短路的问题进行求解
    // 但是问题是如何计算两个字符串之间的距离, 这是一个比较费时的问题
    // 题解使用的思路很巧妙吧, 算是构造了中间的节点
    // int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    //     unordered_map<string, int> existed;
    //     for (int i = 0; i < wordList.size(); i++) existed.insert({wordList[i], i});
    //     if (!existed.count(endWord)) return 0;
    //     if (!existed.count(beginWord)) {
    //         existed.insert({beginWord, wordList.size()});
    //         wordList.push_back(beginWord);
    //     }
    //     queue<int> q; vector<int> used(wordList.size(), -1);
    //     used[existed[beginWord]] = 0; q.push(existed[beginWord]);
    //     while (!q.empty()) {
    //         string x = wordList[q.front()]; q.pop();
    //         if (x == endWord) return used[existed[x]] + 1;
    //         int d = used[existed[x]];
    //         for (char& c: x) {
    //             char temp = c;
    //             for (char i = 'a'; i <= 'z'; i++) {
    //                 if (temp == i) continue; c = i;
    //                 if (existed.count(x)) {
    //                     int index = existed[x];
    //                     if (used[index] == -1) {
    //                         used[index] = d + 1;
    //                         q.push(index);
    //                     }
    //                 }
    //             }
    //             c = temp;
    //         }
    //     }
    //     return 0;
    // }

    // 使用双向队列实现的搜索
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> begin_queue, end_queue, word_set;
        for (auto x: wordList) word_set.insert(x);
        if (!word_set.count(endWord)) return 0;
        begin_queue.insert(beginWord); end_queue.insert(endWord);
        int step = 1;
        while (!begin_queue.empty() && !end_queue.empty()) {
            if (end_queue.size() < begin_queue.size()) {
                swap(begin_queue, end_queue);
            }
            unordered_set<string> s;
            for (string x: begin_queue) {
                for (char & c: x) {
                    char temp = c;
                    for (char i = 'a'; i <= 'z'; i++) {
                        if (i == temp) continue; c = i;
                        if (end_queue.count(x)) return step + 1;
                        if (word_set.count(x)) { 
                            s.insert(x); word_set.erase(x);
                        }
                    }
                    c = temp;
                }
            }
            begin_queue = s;
            step++;
        }
        return 0;

    }

};
// @lc code=end

